package com.zhanghp.class024;

/**
 * <p>无序数组中第K大的元素</p>
 * <a href = "https://leetcode.cn/problems/kth-largest-element-in-an-array/">leetcode</a>
 * <p>在给定的一个整数数组（比如 [3,2,1,5,6,4]）中，要求找到第 k 个最大的元素。这里的“第 k 个最大”意味着从大到小排序后，排在第 k 位置的数。</p>
 *
 * @author zhanghp
 * @since 2024/3/26 10:29
 */
public class RandomizedSelect {
    static class Solution {

        public static int right;
        public static int left;

        // 随机选择算法，时间复杂度O(n)
        public static int findKthLargest(int[] nums, int k) {
            if (nums == null || nums.length == 0) {
                return -1;
            }
            return randomized(nums, nums.length - k);
        }

        public static int randomized(int[] nums, int k) {
            int ans = 0;
            for (int l = 0, r = nums.length - 1; l <= r; ) {
                // index ∈ [left, right]
                partition(nums, l, r, nums[(int) (Math.random() * (r - l + 1)) + l]);
                if (k > right) {
                    l = right + 1;
                } else if (k < left) {
                    r = left - 1;
                } else {
                    ans = nums[k];
                    break;
                }
            }
            return ans;
        }


        public static void partition(int[] arr, int l, int r, int val) {
            left = l;
            right = r;
            int i = left;
            while (i <= right) {
                if (arr[i] < val) {
                    swap(arr, left++, i++);
                } else if (arr[i] == val) {
                    i++;
                } else {
                    swap(arr, i, right--);
                }
            }
        }

        /**
         * 交换
         *
         * @param arr  数组
         * @param var1 索引1
         * @param var2 索引2
         */
        public static void swap(int[] arr, int var1, int var2) {
            int temp = arr[var1];
            arr[var1] = arr[var2];
            arr[var2] = temp;
        }

    }
}
